package folder.main.exp0;

// http://www.algolist.com/code/java/Dijkstra's_algorithm

import java.util.PriorityQueue;
import java.util.List;
import java.util.ArrayList;
import java.util.Collections;

class Node implements Comparable< Node >
{
    public final String name;
    public Link[] links;
    public double minDistance = Double.POSITIVE_INFINITY;
    public Node previous;
    
    public Node( String name )
    {
    	this.name = name;
    }
    
    public String toString() { return name; }
    
    public int compareTo( Node node )
    {
        return Double.compare( minDistance, node.minDistance );
    }
}

class Link
{
    public final Node node;
    public final double weight;
    
    public Link( Node node, double weight )
    {
    	this.node = node;
    	this.weight = weight;
    }
}

public class Dijkstra
{
	
    public static void computePaths( Node source )
    {    
        source.minDistance = 0.;
        PriorityQueue< Node > nodeQueue = new PriorityQueue< Node >();
      	nodeQueue.add( source );

		while ( !nodeQueue.isEmpty() )
		{
			Node node1 = nodeQueue.poll();
	
			// Visit each edge exiting u
			for( Link link: node1.links )
			{
				Node node2 = link.node;
				double weight = link.weight;
				double distanceThroughU = node1.minDistance + weight;
			
				if( distanceThroughU < node2.minDistance )
				{
					nodeQueue.remove( node2 );
					node2.minDistance = distanceThroughU;
					node2.previous = node1;
					nodeQueue.add( node2 );
				}
			}
		}
    }

    public static List< Node > getShortestPathTo( Node target )
    {
        List< Node > path = new ArrayList< Node >();
        
        for( Node node = target; node != null; node = node.previous )
            path.add( node );
        
        Collections.reverse( path );
        
        return path;
    }

    public static void main( String[] args )
    {
        Node node0 = new Node( "0" );
        Node node1 = new Node( "1" );
        Node node2 = new Node( "2" );
        Node node3 = new Node( "3" );
        Node node4 = new Node( "4" );

        node0.links = new Link[]{ 	new Link( node1,  5 ), 
        							new Link( node2, 10 ), 
        							new Link( node3,  8 ) };
        
        node1.links = new Link[]{ 	new Link( node0,  5 ), 
        							new Link( node2,  3 ), 
        							new Link( node4,  7 ) };
        
        node2.links = new Link[]{ 	new Link( node0, 10 ), 
        							new Link( node1,  3 ) };
        
        node3.links = new Link[]{ 	new Link( node0,  8 ), 
        							new Link( node4,  2 ) };
        
        node4.links = new Link[]{ 	new Link( node1,  7 ), 
        							new Link( node3,  2 ) };
        
        Node nodes[] = { node0, node1, node2, node3, node4 };
        
        Dijkstra.computePaths( node4 );
        
        for( Node node: nodes )
        {
        	System.out.println( "Distance to " + node + ": " + node.minDistance );
        	List< Node > path = Dijkstra.getShortestPathTo( node );
        	System.out.println( "Path: " + path );
        }
    }

}
